/*
 * leftistTree.h
 * This file is part of Jamming
 *
 * Copyright (C) 2012 - Yi
 *
 * Jamming is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Jamming is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Jamming. If not, see <http://www.gnu.org/licenses/>.
 */


#ifndef __LEFTISTTREE_H__
#define __LEFTISTTREE_H__
#include <functional>
#include <cstring>
#ifdef __DEBUG__
#include <queue>
#include <utility>
#include <iostream>
#endif 
namespace Heap {
    template< class _TypeData ,class _TypeCompare=std::less<_TypeData> > 
    class LeftistTree {
        struct Node {
            _TypeData data;
            int dist;
            Node* left;
            Node* right;
        }; // TODO each node is a subtree -> less speed/memory effective?
        Node* root;
        Node* merge_subtree(Node* ptrRootA,Node* ptrRootB) {
            Node* tmp;
            if(!ptrRootA) return ptrRootB;
            if(!ptrRootB) return ptrRootA;
            if(ptrRootA->data < ptrRootB->data) {tmp=ptrRootA;ptrRootA=ptrRootB;ptrRootB=tmp;} //A always >= B
            //merge B into right of A.
            #ifdef __DEBUG__
            std::cout<<"Merge "<<ptrRootA->right<<" with "<<ptrRootB<<std::endl;
            #endif
            ptrRootA->right=merge_subtree(ptrRootA->right,ptrRootB);
            //swap left/right if dist(left) < dist(right)
            #ifdef __DEBUG__
            std::cout<<"Left "<<ptrRootA->left<<" right "<<ptrRootA->right<<std::endl;
            #endif
            if( !ptrRootA->left || ptrRootA->left->dist < ptrRootA->right->dist) { tmp=ptrRootA->left;ptrRootA->left=ptrRootA->right;ptrRootA->right=tmp;}
            //update dist of root
            if(ptrRootA->right) ptrRootA->dist=1+(ptrRootA->right->dist);
            return ptrRootA;
        };
        void deleteSubtree(Node* ptrNodeToDelete) {
            if(ptrNodeToDelete->left) deleteSubtree(ptrNodeToDelete->left);
            if(ptrNodeToDelete->right) deleteSubtree(ptrNodeToDelete->right);
            #ifdef __DEBUG__
            std::cout<<"Delete "<<ptrNodeToDelete<<":"<<ptrNodeToDelete->data<<std::endl;
            #endif
            if(ptrNodeToDelete) delete ptrNodeToDelete;
        };
        public:
        LeftistTree() {
            root=NULL;
        };
        ~LeftistTree() {
            if(root) deleteSubtree(root);
        }; 
        void merge_in(LeftistTree<_TypeData,_TypeCompare>& treeB) {
            root=merge_subtree(root,treeB.root);
            treeB.root=NULL;
        };  
        void push(_TypeData data) {
           Node* ptrNewNode= new Node;
           ptrNewNode->data=data;
           ptrNewNode->dist=0;
           ptrNewNode->left=NULL; //TODO necessary? 
           ptrNewNode->right=NULL;
           #ifdef __DEBUG__
           std::cout<<"Insert "<<data<<std::endl;
           std::cout<<"Root: "<<root<<" New: "<<ptrNewNode<<std::endl;
           #endif
           root=merge_subtree(root,ptrNewNode);
        };
        _TypeData pop() {
            _TypeData data=root->data;
            Node* tmp=root;
            root=merge_subtree(root->left,root->right);
            delete tmp;
            return data;
        };
        _TypeData top() {
            return root->data;
        };
        bool empty() {
            return root? false:true;
        };
        #ifdef __DEBUG__
        int maxdepth(Node* root) {
            if(!root) return 0;
            int left=maxdepth(root->left);
            int right=maxdepth(root->right);
            return left>right? left+1:right+1;
        }
        void print() {
            int depth=maxdepth(root);
            std::queue< std::pair<std::pair<int,int>,Node*> > NodesList;
            Node* ptrNode=root;
            std::pair<std::pair<int,int>,Node*> pairNode;
            int level=-1,nth=0,last=0;
            //If empty
            if(!ptrNode) {std::cout<<"Heap Empty."<<std::endl;return;}
            NodesList.push(std::make_pair(std::make_pair(level+1,nth),root));
            while( ! NodesList.empty()) {
                pairNode=NodesList.front();
                NodesList.pop();
                if(pairNode.first.first > level) {
                    //enter new level
                    std::cout<<std::endl<<"Level "<<level+1<<" : ";
                    //std::cout<<(1<<(depth-level-2))-1<<","<<(1<<(depth-level-1))-1;
                    for(register int i=0;i<(1<<(depth-level-2))-1;i++) std::cout<<" ";
                    last=0;
                }
                level=pairNode.first.first;nth=pairNode.first.second;ptrNode=pairNode.second;
                for(register int i=0;i<((1<<(depth-level)))*(nth-last)-1;i++) std::cout<<" ";
                if(ptrNode) std::cout<<ptrNode->data;
                else std::cout<<"x";
                //std::cout<<","<<nth<<","<<last;
                last=nth;
                if( ptrNode->left) NodesList.push(std::make_pair(std::make_pair(level+1,2*nth),ptrNode->left));
                if( ptrNode->right) NodesList.push(std::make_pair(std::make_pair(level+1,2*nth+1),ptrNode->right));
            }
            std::cout<<std::endl;
        };
        #endif

    };
};

#endif /* __LEFTISTTREE_H__ */

